use std::cell::RefCell;
use std::rc::{Rc, Weak};

type ListData = *mut i32;

struct ListEntry {
    data: ListData,
    prev: RefCell<Option<Weak<ListEntry>>>,
    next: RefCell<Option<Rc<ListEntry>>>,
}

impl ListEntry {
    fn new(data: ListData) -> Rc<ListEntry> {
        Rc::new(ListEntry {
            data,
            prev: RefCell::new(None),
            next: RefCell::new(None),
        })
    }
}

fn list_append(list: &mut Option<Rc<ListEntry>>, data: ListData) -> Option<Rc<ListEntry>> {
    let new_entry = ListEntry::new(data);
    match list {
        Some(ref mut head) => {
            let mut rover = head.clone();
            loop {
                let next = rover.next.borrow().clone();
                match next {
                    Some(ref next_entry) => {
                        rover = next_entry.clone();
                    }
                    None => {
                        rover.next.replace(Some(new_entry.clone()));
                        new_entry.prev.replace(Some(Rc::downgrade(&rover)));
                        break;
                    }
                }
            }
            Some(new_entry)
        }
        None => {
            *list = Some(new_entry.clone());
            Some(new_entry)
        }
    }
}

fn list_prepend(list: &mut Option<Rc<ListEntry>>, data: ListData) -> Option<Rc<ListEntry>> {
    let new_entry = ListEntry::new(data);
    match list {
        Some(ref mut head) => {
            new_entry.next.replace(Some(head.clone()));
            head.prev.replace(Some(Rc::downgrade(&new_entry)));
            *list = Some(new_entry.clone());
            Some(new_entry)
        }
        None => {
            *list = Some(new_entry.clone());
            Some(new_entry)
        }
    }
}

fn list_free(list: &mut Option<Rc<ListEntry>>) {
    while let Some(head) = list.take() {
        if let Some(next) = head.next.borrow().clone() {
            *list = Some(next);
        }
    }
}

fn list_next(entry: &Rc<ListEntry>) -> Option<Rc<ListEntry>> {
    entry.next.borrow().clone()
}

fn list_prev(entry: &Rc<ListEntry>) -> Option<Weak<ListEntry>> {
    entry.prev.borrow().clone()
}

fn list_data(entry: &Rc<ListEntry>) -> ListData {
    entry.data
}

fn list_nth_entry(list: &Option<Rc<ListEntry>>, n: usize) -> Option<Rc<ListEntry>> {
    let mut rover = list.clone();
    for _ in 0..n {
        rover = rover.and_then(|r| list_next(&r));
    }
    rover
}

fn list_nth_data(list: &Option<Rc<ListEntry>>, n: usize) -> ListData {
    list_nth_entry(list, n).map(|entry| list_data(&entry)).unwrap_or(std::ptr::null_mut())
}

fn list_length(list: &Option<Rc<ListEntry>>) -> usize {
    let mut length = 0;
    let mut rover = list.clone();
    while let Some(entry) = rover {
        length += 1;
        rover = list_next(&entry);
    }
    length
}

fn list_remove_entry(list: &mut Option<Rc<ListEntry>>, entry: &Rc<ListEntry>) -> bool {
    if let Some(prev) = list_prev(entry) {
        if let Some(prev_rc) = prev.upgrade() {
            *prev_rc.next.borrow_mut() = list_next(entry);
        }
    } else {
        *list = list_next(entry);
    }
    if let Some(next) = list_next(entry) {
        *next.prev.borrow_mut() = list_prev(entry);
    }
    true
}

fn list_remove_data(list: &mut Option<Rc<ListEntry>>, data: ListData) -> bool {
    let mut rover = list.clone();
    while let Some(entry) = rover {
        if list_data(&entry) == data {
            list_remove_entry(list, &entry);
            return true;
        }
        rover = list_next(&entry);
    }
    false
}

fn int_equal(a: ListData, b: ListData) -> bool {
    unsafe { *a == *b }
}

fn int_compare(a: ListData, b: ListData) -> std::cmp::Ordering {
    unsafe { (*a).cmp(&*b) }
}

fn list_sort(list: &mut Option<Rc<ListEntry>>, compare: fn(ListData, ListData) -> std::cmp::Ordering) {
    let mut vec: Vec<ListData> = Vec::new();
    while let Some(entry) = list.take() {
        vec.push(list_data(&entry));
        if let Some(next) = list_next(&entry) {
            *list = Some(next);
        }
    }
    vec.sort_by(|a, b| compare(*a, *b));
    for &data in vec.iter() {
        list_append(list, data);
    }
}

fn list_find_data(list: &Option<Rc<ListEntry>>, data: ListData, equal: fn(ListData, ListData) -> bool) -> Option<Rc<ListEntry>> {
    let mut rover = list.clone();
    while let Some(entry) = rover {
        if equal(list_data(&entry), data) {
            return Some(entry);
        }
        rover = list_next(&entry);
    }
    None
}

fn list_to_array(list: &Option<Rc<ListEntry>>) -> Option<*mut ListData> {
    let length = list_length(list);
    let array = unsafe { std::alloc::alloc(std::alloc::Layout::array::<ListData>(length).unwrap()) as *mut ListData };
    let mut rover = list.clone();
    let mut i = 0;
    while let Some(entry) = rover {
        unsafe { *array.offset(i) = list_data(&entry) };
        i += 1;
        rover = list_next(&entry);
    }
    Some(array)
}

fn main() {
    // Define your main logic here
}